package sort;

import java.util.Arrays;
import java.util.Random;

/**
 * @Auther: MFM
 * @Date: 2022/3/27 - 03 - 27 - 18:01
 * @version: 1.0
 */

public class LinearTimeSort {

    public void countSort(int[] arr){
        if (arr == null){
            return;
        }

        int maxNum = arr[0];
        int minNum = arr[0];

        for (int num:arr) {
            if (maxNum < num){
                maxNum = num;
            }

            if (minNum > num){
                minNum = num;
            }
        }

        int[] sortedArr = new int[maxNum - minNum + 1];

        for (int i = minNum; i < maxNum+1; i++) {
            for (int j = 0; j < arr.length; j++) {
                if (arr[j] == i){
                    sortedArr[i-minNum]++;
                }
            }
        }

        int[] finArr = new int[arr.length];

        int index = 0;

        for (int i = 0; i < sortedArr.length; i++) {
            for (int j = 0; j < sortedArr[i]; j++) {

                    finArr[index++] = minNum + i;

            }
        }


        System.arraycopy(finArr,0,arr,0,arr.length);
    }

    //基数排序
    public void radixSort(int[] arr){

    }

    //桶排序
    public void bucketSort(int[] arr){
        if (arr==null){
            return;
        }

        //最大值和最小值
        int max = arr[0];
        int min = arr[0];

        //遍历数组 找出最大值和最小值
        for (int i = 0; i < arr.length; i++) {
            if (max<arr[i]){
                max = arr[i];
            }
            if (min>arr[i]){
                min = arr[i];
            }
        }

        //每个桶的容量（范围）
        int bucket = (max - min) / arr.length + 1;

        //桶的数量
        int nums = (max - min ) / bucket + 1;

        //记录索引
        int index = 0;

        //每一个桶是一个数组  所有桶的合计是一个数组
        int[][] bucketArr = new int[nums][arr.length-1];

        //将元素组的所有数字根据不同范围放入不同的桶中
        for (int i = 0; i < nums; i++) {
            for (int j = 0; j < arr.length; j++) {
                if (arr[j] >= min + i * bucket && arr[j] < min + (i+1) * bucket ){
                    bucketArr[i][index] = arr[j];
                    index++;
                }
            }
            index = 0;
        }

        //在桶内使用希尔排序
        for (int i = 0; i < bucketArr.length; i++) {
                new InsertionSort().shellSort(bucketArr[i]);
        }

        //重复利用记录索引
        index = 0;

        //将桶内的所有元素放入原数组 （当元素为零是自动 排除 所以待排数组中 应 没有零 局限）
        for (int i = 0; i < bucketArr.length; i++) {
            for (int j = 0; j < arr.length-1; j++) {
                if (bucketArr[i][j]!=0){
                    arr[index] = bucketArr[i][j];
                    index++;
                }
            }
        }

    }

    public static void main(String[] args) {
        /*
         * 测试结果
         * 1000000 排序所用时间为
         * 计数排序 数组中最大数和最小数差距越大用时越长
         * 桶排序   创建数组太大 超过int范围 创建了负数数组NegativeArraySizeException
         * 基数排序
         * */
        int[] arr = new int[1000000];
        Random r = new Random();


        for (int i = 0; i < arr.length; i++) {
            arr[i] = r.nextInt();
        }

        long start = System.currentTimeMillis();

        new LinearTimeSort().bucketSort(arr);

        long end = System.currentTimeMillis();

        System.out.println(end - start);
//        int[] arr = {15,5,2,7,12,6,1,4,3,9,8};
//
//        new LinearTimeSort().bucketSort(arr);
//
//        for (int a : arr
//        ) {
//            System.out.print(a + " ");
//        }
    }
}
